This invention relates to first-in, first-out (FIFO) data structures, and in particular to multidimensional, nonlinear FIFO structures.
FIG. 1 shows a conventional flow-through FIFO circuit 50. In circuit 50, a data item is received on an input node 55, where a first stage 60(1) accepts the data item and passes it to a second stage 60(2), and so on to a third stage 60(3) and a fourth stage 60(4), or more, until the data item is output on output node 56 in the order in which it was received. An interconnect 58 in the form of wires or other type of data connection links pairs of successive stages.
Usually, FIFO circuits use some form of control mechanism to control the sequential transition of data items from one stage to another. FIG. 2 is a simplified circuit diagram that illustrates a conventional linear first-in, first-out (FIFO) data structure 100 with control circuitry. FIFO data structure 100 includes a data path 101, on which data items are sequentially moved, and a control path 102. A data item can be any type of information signal and can comprise of any number of bits, words, etc. Control signals are digital signals or other signals that reflect the state of data path 101, and direct the data path structures to move data items according to a predetermined protocol.
In the data path structure shown in FIG. 2, a plurality of data path cells 105 are interconnected in series. A first data item is received at an input to a first data path cell 105(1), where the first data item is processed and output to a next data path cell 105(2). The data item is processed in the next data path cell and the routine is repeated again as the data item is again output to a next data path cell 105(3). The state of each data path cell 105 is monitored and controlled by a corresponding control cell 110. In a simplistic example, control cell 110(1) detects when data path cell 105(1) has received a data item, and then directs data path cell 105(1) to process the data item and send it to the next data path cell 105(2). Control cell 110(1) sends command and status information to the next control cell 110(2) in the series, so that cell 110(2) is able to detect when the data item is received in the next data path cell 105(2).
One problem that arises in linear FIFO data structures is a high latency from first input to final output. As each processing stage must wait for the output of a stage before it, delays in each stage are cumulative. Thus, more stages in the FIFO leads to a higher latency. Another problem with linear FIFO data structures is high energy consumption. For a linear flow-through FIFO, the energy consumption per data item that flows through the FIFO is approximately proportional to the total number of stages in the FIFO. More stages in a FIFO leads to more energy consumption.
Generally, the present invention provides a method and apparatus for a multi-dimensional, low-latency, energy efficient and high throughput data structure that exhibits FIFO behavior.
In a first aspect of the invention, a data structure includes an N-row-by-M-column array of data path cells, where N and M are integers greater than one. A first cell of a first row of the array is configured to receive an ordered stream of data items. A control circuit is coupled to the array and configured to sequentially move individual data items to particular cells in the array. In one sequence, data items flow sequentially into the first row of the array (with M cells per row), flow separately down the M columns of the array, and then flow sequentially through the M cells of the Nth row to an output from the Mth cell of the Nth row in the array.
In a second aspect of the invention, a nonlinear FIFO data structure includes an input data path cell configured to receive an ordered stream of data items via an input interconnect; an output data path cell configured to receive the ordered stream of data via an output interconnect; a plurality of intermediate data path cells connected between the input data path cell and the output data path cell in an array of rows and columns, wherein a first row is coupled to the input data cell and a last row is coupled to the output data path cell; a plurality of intermediate interconnects connecting each intermediate cell with intermediate cells adjacent to it; and control circuitry coupled to the input, output and intermediate interconnects configured to sequentially move individual data items from the input cell to particular data path cells in the first row, separately down columns of the data path cells, and then sequentially from particular data path cells of the last row to the output cell, such that the individual data items are output to the output cell in the order received at the input cell.
In a third aspect of the invention, a FIFO data structure includes an input pass gate configured to receive an ordered stream of data items from an input cell; an N-row-by-M-column array of data path cells, where N is greater than one and M is greater than one, the array of data path cells having an input row coupled to the input cell; a plurality of pass gates, each pass gate interconnecting adjacent cells in the input row, adjacent cells in an output row, and cells adjacent to the remaining cells in the array, each pass gate configured to receive a data item from a previous cell and sequentially pass the received data item to a next cell according to a predetermined sequence; a control circuit that controls the individual movement of data items through the plurality of pass gates, first through successive pass gates of the input row cells, from selected input-row cells through successive pass gates of columns comprising, in part, the remaining cells, and then through successive pass gates of the output row; and an output pass gate coupled to the Mth-row, Nth-column cell, configured to output the processed data items, wherein the control circuit follows the predetermined sequence such that the data items are output in the order received at the input pass gate.
In a fourth aspect of the invention, a data structure having an N-row-by-M-column array of communication cells includes a data path circuit having a plurality of sticky buffers, one to each cell, and a plurality of pass gates, configured to communicatively couple adjacent cells in an input row of the array, adjacent cells in an output row of the array, and any cell adjacent to other cells in the array; and a control circuit that controls movement of data items in the data path circuit from one sticky buffer to a next sticky buffer, by making a pass gate therebetween transparent.
In a fifth aspect of the invention, a two-dimensional first-in, first-out (FIFO) data structure includes an N-row-by-M-column array of individual FIFO cells having a data path, including a data buffer within each FIFO cell, and a pass gate between adjacent cells; and a control circuit in communication with the data path and configured to control data propagation along various predefined routes in the data path.
In a sixth aspect of the invention, an asynchronous pipeline module for use in a multi-dimensional FIFO data structure includes a NAND logic gate having a first input configured to receive a first control signal, a second input configured to receive an inverse of a second control signal and an output; a first inverter coupled between the output of the NAND logic gate and an associated pass gate so that the pass gate receives the inverse of the output of the NAND logic gate; a first transistor having a gate coupled to the inverse of the output of the NAND logic gate, a drain coupled to the first control signal and a source coupled to ground; a second transistor having a gate coupled to the output of the NAND logic gate, a drain coupled to the second control signal and a source coupled to a power supply; and at least one drive transistor having a gate coupled to the gate of either the first or second transistor, a source coupled to either ground or the power supply, respectively, and a drain that embodies an output of the asynchronous pipeline module.
In a seventh aspect of the invention, a method of moving data items through a two-dimensional first-in, first-out FIFO arranged in an N-row-by-M-column array of individual FIFO cells includes the steps of moving a first data item into an input cell located in an input row and an input column of the array; moving the first data item through cells in the input row and into an Mth cell in the Mth column; moving the first data item down through cells in the Mth column and into an output cell in the Nth row; moving the first data item out of the output cell; moving every k-th data item, where 0 less than k less than M+1, into the input cell; moving the k-th data item through cells in the input row and into an (M+1xe2x88x92k)th cell in the (M+1xe2x88x92k)th column; moving every k-th data item down through cells in the (M+1xe2x88x92k)th column and into the (M+1xe2x88x92k)th cell in the Nth row; moving every k-th data item into the output cell in the Nth row; and moving every k-th data item out of the output cell.
In an eighth aspect of the invention, a multi-dimensional first-in, first-out (FIFO) data structure includes a distributor having a first plurality of data cells configured to receive data items, one data item at a time; a plurality of FIFOs having inputs individually coupled to the first plurality of cells of the distributor; and a collector having a second plurality of cells individually coupled to outputs of the FIFOs, the collector configured to collect the data items, one data item at a time. In this embodiment data items are distributed and collected, via the plurality of FIFOs, according to a predefined round-robin scheme as will be explained in more detail below in the detailed description of the invention.